package pers.qianyu.month_202012.date_20201202;

import java.util.*;

/**
 * 491. 递增子序列
 * https://leetcode-cn.com/problems/increasing-subsequences/
 *
 * @author mizzle rain
 * @date 2020-12-02 17:53
 */
public class FindSubsequences {
    private Set<List<Integer>> res = new HashSet<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<>();
        }
        for (int i = 0; i < nums.length; i++) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(nums[i]);
            recur(nums, i, list);
        }
        return new ArrayList<>(res);
    }

    private void recur(int[] nums, int index, ArrayList<Integer> list) {
        if (index >= nums.length) {
            return;
        }
        for (int i = index + 1; i < nums.length; i++) {
            if (nums[i] >= list.get(list.size() - 1)) {
                list.add(nums[i]);
                res.add(new ArrayList<>(list));
                recur(nums, i, list);
                list.remove(Integer.valueOf(nums[i]));
            }
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> result = new FindSubsequences()
                .findSubsequences(new int[]{4, 6, 7, 7});
        result.forEach(System.out::println);
    }
}
